package com.hecun.algorithm.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Demo1 {
	
	public static void main(String[] args) {
		TreeNode r1 = new TreeNode(1);
		TreeNode r2 = new TreeNode(2);
		TreeNode r3 = new TreeNode(3);
		TreeNode r4 = new TreeNode(4);
		TreeNode r5 = new TreeNode(5);
		TreeNode r6 = new TreeNode(6);
		
		r1.left = r2;
		r1.right = r3;
		r2.left = r4;
		r2.right = r5;
		r3.right = r6;
		
	}
	
	/** 
     * 求二叉树中的节点个数递归解法： O(n) 
     * （1）如果二叉树为空，节点个数为0  
     * （2）如果二叉树不为空，二叉树节点个数 = 左子树节点个数 + 
     *            右子树节点个数 + 1 
     */  
	public static int getNodeNumRec(TreeNode root){
		if(root == null){
			return 0;
		} else {
			return getNodeNumRec(root.left) + getNodeNumRec(root.right) + 1;
		}
	}
	
	/** 
     *  求二叉树中的节点个数迭代解法O(n)：基本思想同LevelOrderTraversal， 
     *  即用一个Queue，在Java里面可以用LinkedList来模拟  
     */ 
	public static int getNodeNum(TreeNode root){
		if(root == null){
			return 0;
		}
		//根元素,所以节点数为1
		int count = 1;
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		
		while(!queue.isEmpty()){
			TreeNode cur = queue.remove();
			if(cur.left != null){
				queue.add(cur.left);
				count++;
			}
			if(cur.right != null){
				queue.add(cur.right);
				count++;
			}
		}
		
		return count;
	}
	
	/** 
     * 求二叉树的深度（高度） 递归解法： O(n) 
     * （1）如果二叉树为空，二叉树的深度为0  
     * （2）如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1 
     */  
	public static int getDepthRec(TreeNode root){
		if(root == null){
			return 0;
		}
		
		int letfDepth = getDepthRec(root.left);
		int rightDepth = getDepthRec(root.right);
		return Math.max(letfDepth, rightDepth) + 1;	
	}
	
	/** 
     * 求二叉树的深度（高度） 迭代解法： O(n) 
     * 基本思想同LevelOrderTraversal，还是用一个Queue 
     */  
	public static int getDepth(TreeNode root){
		if (root == null) {
			return 0;
		}
		
		int depth = 0;	//深度
		int currentLevelNodes = 1;	//当前层, node的数量
		int nextLevelNodes = 0;		//下一层, node的数量
		
		Queue<TreeNode> queue = new LinkedList<>();
		queue.add(root);
		
		while(!queue.isEmpty()){
			TreeNode cur = queue.remove();	//从队头位置移除
			currentLevelNodes--;	//减少当前层的节点数量
			//把左右子树入列
			if(cur.left != null){
				queue.add(cur.left);
				nextLevelNodes++;
			}
			if (cur.right != null) {
				queue.add(cur.right);
				nextLevelNodes++;
			}
			
			//已经遍历完当前层全部节点
			if(currentLevelNodes == 0){
				depth++;
				currentLevelNodes = nextLevelNodes;
				nextLevelNodes = 0;
			}
		}
		
		return depth;
	}
	
	/** 
     * 前序遍历，中序遍历，后序遍历 前序遍历递归解法：  
     * （1）如果二叉树为空，空操作  
     * （2）如果二叉树不为空，访问根节点，前序遍历左子树，前序遍历右子树 
     */  
	public static void preOrderTraversalRec(TreeNode root){
		if (root == null) {
			return;
		}
		
		System.out.println(root.val + " ");
		preOrderTraversalRec(root.left);
		preOrderTraversalRec(root.right);
	}
	
	/** 
	 *  前序遍历: 根 左 右
     *  前序遍历迭代解法：用一个辅助stack，总是把右孩子放进栈.
     *  当入栈顺序按照根 右 左进行入栈时，根先出栈，然后出栈左子节点，最后出栈右子节点。
     *  http://www.youtube.com/watch?v=uPTCbdHSFg4 
     */  
	public static void preOrderTraversal(TreeNode root){
		if (root == null) {
			return;
		}
		
		Stack<TreeNode> stack = new Stack<>();
		stack.push(root);
		
		while(!stack.isEmpty()){
			TreeNode cur = stack.pop();	//出栈, 出来的是栈顶元素
			System.out.println(cur.val + " ");

			//关键点：要先压入右孩子，再压入左孩子，这样在出栈时会先打印左孩子再打印右孩子 
			if (cur.right != null) {
				stack.push(cur.right);
			}
			if(cur.left != null){
				stack.push(cur.left);
			}
		}
	}
	
	/** 
     * 中序遍历递归解法  
     * （1）如果二叉树为空，空操作。  
     * （2）如果二叉树不为空，中序遍历左子树，访问根节点，中序遍历右子树 
     */  
	public static void inOrderTraversalRec(TreeNode root) {
		if (root == null) {
			return;
		}
		
		inOrderTraversalRec(root.left);
		System.out.println(root.val + " ");
		inOrderTraversalRec(root.right);
	}
	
	 /** 
	  * 中序遍历: 左 根 右
      * 中序遍历迭代解法 ，用栈先把根节点的所有左孩子都添加到栈内，然后输出栈顶元素，再处理栈顶元素的右子树 
      * http://www.youtube.com/watch?v=50v1sJkjxoc 
      */ 
	public static void inOrderTraversal(TreeNode root) {
		if (root == null) {
			return;
		}
		
		//构造一个栈,存放根节点的所有左子树
		Stack<TreeNode> stack = new Stack<>();
		TreeNode cur = root;
		
		while (true) {
			while (cur != null) {
				stack.push(cur);
				cur = cur.left;
			}
			
			if (stack.isEmpty()) {
				break;
			}
			
			// 因为此时已经没有左孩子了，所以输出栈顶元素  
			cur = stack.pop();
			System.out.println(cur.val + " ");
			cur = cur.right;	// 准备处理右子树  
		}
	}
	
	/** 
     * 后序遍历递归解法  
     * （1）如果二叉树为空，空操作  
     * （2）如果二叉树不为空，后序遍历左子树，后序遍历右子树，访问根节点 
     */  
	public static void postOrderTraversalRec(TreeNode root) {
		if (root == null) {
			return;
		}
		
		postOrderTraversalRec(root.left);
		postOrderTraversalRec(root.right);
		System.out.println(root.val + " ");
	}
	
	/** 
     *  后序遍历迭代解法 
     *  http://www.youtube.com/watch?v=hv-mJUs5mvU 
     */ 
	public static void postOrderTraversal(TreeNode root) {
		if (root == null) {
			return;
		}
		
		Stack<TreeNode> s = new Stack<>();
		Stack<TreeNode> output = new Stack<>();
		
		s.push(root);
		
		while (!s.isEmpty()) {	// 确保所有元素都被翻转转移到第二个stack  
			TreeNode cur = s.pop();	// 把栈顶元素添加到第二个stack 
			output.push(cur);
			
			if (cur.left != null){
				s.push(cur.left);
			}
			if (cur.right != null) {
				s.push(cur.right);
			}
		}
		
		while (!output.isEmpty()) {
			System.out.println(output.pop().val + " ");
		}
	}
	
	/** 
     * 分层遍历二叉树（按层次从上往下，从左往右）迭代 
     * 相当于广度优先搜索，使用队列实现。队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出一个节点,若左子节点或右子节点不为空，将其压入队列 
     */  
	public static void levelTraversal(TreeNode root) {
		if (root == null) {
			return;
		}
		
		LinkedList<TreeNode> queue = new LinkedList<>();
		queue.push(root);
		
		while (!queue.isEmpty()) {
			TreeNode cur = queue.removeFirst();
			System.out.println(cur.val + " ");
			
			if (cur.left != null) {
				queue.push(cur.left);
			}
			
			if (cur.right != null) {
				queue.push(cur.right);
			}
		}
	}
}
















